package com.alex.algorithm.iguide.queue;

import com.google.common.collect.Lists;

import java.util.LinkedList;

public class MaxWindowValue {

    public static void main(String[] args) {
        int[] resArr = maxWinVal(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        for (int i = 0; i < resArr.length; ++i) {
            System.out.println(resArr[i]);
        }
    }

    public static int[] maxWinVal(int[] array, int w) {
        if (array == null || array.length == 0 || array.length < w) {
            return null;
        }
        LinkedList<Integer> list = Lists.newLinkedList();
        int[] result = new int[array.length - w + 1];
        int index = 0;
        for (int i = 0; i < array.length; ++i) {
            while (!list.isEmpty() && array[i] > array[list.peekLast()]) {
                list.pollLast();
            }
            list.push(i);
            if (!list.isEmpty() && list.peekFirst() == i - w) {
                list.pollFirst();
            }
            if (i >= w - 1) {
                result[index++] = array[list.peekLast()];
            }
        }
        return result;
    }
}
